/**
 * 顺序表实现队列
 */
#include <iostream>
#include <stdexcept>

using namespace std;

template <typename T>
class Queue
{
private:
    T *data;       // 元素类型
    int front;     // 队首元素索引
    int rear;      // 队尾元素索引
    int capacity;  // 容量
    void resize(); // 扩容

public:
    Queue() : data(new T[10]), front(0), rear(0), capacity(10) {}
    ~Queue();

    void enqueue(T element);// 入队
    T dequeue();            // 出队
    T getFront() const;     // 获取头
    int getSize() const;    // 获取大小
    void print();           // 打印
};

template <typename T>
void Queue<T>::resize()
{
    T *newData = new T[capacity * 2];   // 两倍扩容出一个新的头
    for (int i = 0; i < rear; ++i) 
    {
        newData[i] = data[i];
    }
    delete[] data;
    data = newData;
    capacity *= 2;
}

template <typename T>
Queue<T>::~Queue()
{
    delete[] data;
}

template <typename T>
void Queue<T>::enqueue(T element)
{
    if (rear == capacity)
    {
        resize();
    }
    data[rear++] = element;
}

template <typename T>
T Queue<T>::dequeue()
{
    if (front == rear)
    {
        throw std::underflow_error("Queue is empty");
    }
    return data[front++];   // 返回头并且将头后移（删除）
}

template <typename T>
T Queue<T>::getFront() const
{
    if (front == rear)
    {
        throw std::underflow_error("Queue is empty");
    }
    return data[front];   
}

template <typename T>
int Queue<T>::getSize() const
{
    return rear - front;
}

template <typename T>
void Queue<T>::print()
{
    T *pTemp = data;
    while (pTemp)
    {
        pTemp++;
    }
    
    while (rear) {
        cout << getFront() << " ";
        dequeue();
    }
}

int main()
{
    Queue<int> q1;
    q1.enqueue(1);
    q1.enqueue(12);
    q1.enqueue(23);
    q1.enqueue(34);
    q1.enqueue(45);
    q1.enqueue(56);

    cout << "队列头：" << q1.getFront() << "队列大小：" << q1.getSize() << endl;
    q1.dequeue();
    cout << "队列头：" << q1.getFront() << "队列大小：" << q1.getSize() << endl;
 
    return 0;
}
